package Test;

import java.util.HashMap;

public class LeetCodeTest {
	public static void main(String[] args){
		//System.out.println(RomanToInt("DCXXI"));
		System.out.println(LongestCommonPrefix1(new String[]{"aa","a"}));
	}
	public static String intToRoman(int num) {
		int[] value = new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
		String[] symbol = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL",  
										"X", "IX", "V", "IV","I" }; 
		StringBuilder result = new StringBuilder();
		for(int i = 0;i < value.length; i++){
			while(num >= value[i]){
				result = result.append(symbol[i]);
				num = num - value[i];
			}
		}
        return result.toString();
    }
	public static int RomanToInt(String str){
		if(str.length() == 0){return 0;}
		str = str.toUpperCase();
		HashMap<Character, Integer> map= new HashMap<>();
		map.put('M', 1000);
		map.put('D', 500);
		map.put('C', 100);
		map.put('L', 50);
		map.put('X', 10);
		map.put('V', 5);
		map.put('I', 1);
		int result = map.get(str.charAt(str.length()-1));
		for(int i = str.length()-2; i >= 0 ; i--){
			if(map.get(str.charAt(i)) < map.get(str.charAt(i+1))){
				result = result - map.get(str.charAt(i));
			}else{
				result = result + map.get(str.charAt(i));
			}
		}
		return result;
	}
	public static String LongestCommonPrefix1(String[] strs){
		/*int minLen = strs[0].length();
		for(int i=1;i<strs.length;i++){
			if(strs[i].length()<minLen){
				minLen = strs[i].length();
			}	
		}*/
		if(strs.length == 0){return "";}
		if(strs.length == 1){return strs[0];}
		String result = strs[0];
		for(int i=1;i<strs.length;i++){
			if(strs[i].length()<1 || strs[i].length()<1){return "";}
			result = LongPrefix(result,strs[i]);
		}
		
		return result;
	}
	public static String LongPrefix(String s1,String s2){
		if(s1.length()<1||s1.length()<1){
			return "";
		}
		int minLen = (s1.length() > s2.length())?s2.length():s1.length();
		
		StringBuilder prefix = new StringBuilder();
		for(int i = 0;i< minLen;i++){
			if(s1.charAt(i) == s2.charAt(i)){
				prefix = prefix.append(s1.charAt(i));
			}else{
				break;
			}
		}
		return prefix.toString();
	}
	public static String LongestCommonPrefix2(String[] strs){
		if(strs.length == 0){return "";}
		if(strs.length == 1){return strs[0];}
		int minLen = strs[0].length();
		for(int i=1;i<strs.length;i++){
			if(strs[i].length()<minLen){
				minLen = strs[i].length();
			}	
		}
		if(minLen < 1){return "";}
		StringBuilder result = new StringBuilder();
		for(int index = 0 ;index<minLen;index++){
			for(int i = 0;i<strs.length-1;i++){
				if(strs[i].charAt(index) != strs[i+1].charAt(index)){
					return result.toString();
				}
			}
			result = result.append(strs[0].charAt(index));
		}
		return result.toString();
	}
}
